package com.yuan.algorithms.动态规划;

/*
 Input
 4
 1 1
 2 5
 3 8
 4 9

 Output
 10
 */
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author YouYuan
 * @contact 1265161633@qq.com
 * @date 2016年3月12日 下午1:21:08
 * @descript 算法导论-动态规划-钢条切割问题
 */
public class CutRod {

	static Scanner in = new Scanner(System.in);

	public static void main(String[] args) {
		while (in.hasNext()) {
			int n = in.nextInt();// 需要切割的长度
			int[] length = new int[n + 1];
			int[] price = new int[n + 1];
			for (int i = 1; i <= n; i++) {
				// 接收长度以及对应的价格
				length[i] = in.nextInt();
				price[i] = in.nextInt();
			}
			System.out.println(memoizedCutRod(price, n));
			System.out.println(buttomUpCutRod(price, n));
		}
	}

	/**
	 * 自底向上求解
	 * 
	 * @param price
	 * @param n
	 * @return
	 */
	private static int buttomUpCutRod(int[] price, int n) {
		int[] r = new int[n + 1];//存储最优切割收益
		int[] s = new int[n + 1];//存储最优切割的第一段切割长度
		int q = 0;
		for (int i = 1; i <= n; i++) {
			q = Integer.MIN_VALUE;//初始化最大收益q
			for (int j = 1; j <= i; j++) {// 循环求解最大收益
				if (q < price[j] + r[i - j]) {
					q = price[j] + r[i - j];
					s[i] = j;//长度为i的钢条的最优切割的第一段为j
				}
				//q = Math.max(q, price[j] + r[i - j]);
			}
			r[i] = q;//保存最优收益
		}
		prinCutRodSolution(n, s);//打印最优切割的切割方法
		return r[n];//返回长度为n时的最大收益
	}

	private static void prinCutRodSolution(int n, int[] s) {
		while(n > 0) {
			//打印n的最佳切割的第一段s[n]，再打印剩下的部分的最佳切割方案
			System.out.println("-------------------");
			System.out.println("最优切割方案:");
			System.out.print(s[n]+" ");
			n -= s[n];
		}
		System.out.println();
		System.out.println("-------------------");
	}

	/**
	 * 带备忘的自顶向下求解
	 * 
	 * @param price
	 * @param n
	 * @return
	 */
	private static int memoizedCutRod(int[] price, int n) {
		int[] r = new int[n + 1];// 备忘数组，用于存储长度为n的切割最大收益
		Arrays.fill(r, Integer.MIN_VALUE);// 将收益初始化为最小值
		return memoizedCutRodAux(price, n, r);
	}

	private static int memoizedCutRodAux(int[] price, int n, int[] r) {
		int q;
		if (r[n] >= 0) {// 如果最大收益已经存在了，则直接返回，避免重复递归计算
			return r[n];
		}
		if (n == 0) {
			q = 0;
		} else {
			q = Integer.MIN_VALUE;
			for (int i = 1; i <= n; i++) {
				/*
				 * 循环求解最大收益
				 */
				q = Math.max(q, price[i] + memoizedCutRodAux(price, n - i, r));
			}
		}
		r[n] = q;// 记录当前已经求解的最大收益
		return q;
	}

}
